function listToTree(list, mk = "id", pk = "parentId", childrenKey = "children") {

    if (!list || list.length < 1) return list;
    let rootNodes = treeUtils.findAllRoots(list, mk, pk)
    if (!rootNodes || rootNodes.length < 1) return list;
    for (let i = 0; i < rootNodes.length; i++) {
        let item = rootNodes[i];
        let childNodes = treeUtils.findChildren(list, item[mk], mk, pk, childrenKey)
        if (!childNodes || childNodes.length < 1) continue
        if (!item[childrenKey]) item[childrenKey] = []
        item[childrenKey] = item[childrenKey].concat(childNodes)
    }
    return rootNodes
}

function findAllRoots(list, mk, pk) {
    let nodePk = {};
    let rootNodes = [];
    for (let i = 0; i < list.length; i++) {
        let item = list[i];
        if (!item[mk]) continue
        if (nodePk[item[mk]]) continue;
        nodePk[item[mk]] = item;
    }
    for (let i = 0; i < list.length; i++) {
        let item = list[i];
        if (nodePk[item[pk]]) continue;
        rootNodes.push(item)
    }
    return rootNodes;
}

function findChildren(list, nodeMkValue, mk, pk, childrenKey) {
    let nodes = [];
    if (!list || list.length < 1) return nodes;
    for (let i = 0; i < list.length; i++) {
        let item = list[i];
        if (item[pk] !== nodeMkValue) continue
        nodes.push(item)
        // list.splice(i, 1);
        let childNodes = treeUtils.findChildren(list, item[mk], mk, pk, childrenKey)
        if (!childNodes || childNodes.length < 1) continue
        if (!item[childrenKey]) item[childrenKey] = []
        item[childrenKey] = item[childrenKey].concat(childNodes)
    }
    return nodes;
}

function treeToList(tree, childrenKey = "children", filter) {
    let result = [];
    if (filter === null || filter === undefined) {
        filter = (item, index, array) => true;
    }
    if (!(filter instanceof Function)) {
        throw Error('filter must be a function');
    }


    let item;

    function _forTree(treeList) {
        if (treeList === null || treeList === undefined || treeList.length < 1) {
            return;
        }
        for (let i = 0; i < treeList.length; i++) {
            item = treeList[i];
            if (filter(item, i, treeList)) {
                result.push(treeList[i]);
            }
            _forTree(treeList[i][childrenKey])
        }
    }

    _forTree(tree)
    return result;

}


const treeUtils = {
    listToTree,
    findAllRoots,
    findChildren,
    treeToList
}

export default treeUtils
